package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import Tree.TreeNode;

public class TreeLevelOrder {

	// 按层次遍历树
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		List<Integer> list = new ArrayList<>();
		if(root == null){
			return res;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		//下一层有多少个结点
		int nextLevel = 0;
		//该层等待打印的结点
		int toBePrint = 1;
		TreeNode temp = null;
		while(!queue.isEmpty()){
			temp = queue.poll();
			if(temp.left != null){
				queue.add(temp.left);
				nextLevel++;
			}
			if(temp.right != null){
				queue.add(temp.right);
				nextLevel++;
			}
			list.add(temp.val);
			toBePrint--;
			if(toBePrint == 0){
				toBePrint = nextLevel;
				nextLevel = 0;
				res.add(new ArrayList<>(list));
				list.clear();
			}
		}
		return res;
	}
	
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		Stack<List<Integer>> res = new Stack<List<Integer>>();
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> list = new ArrayList<>();
		if(root == null){
			return res;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		int nextLevel = 0;
		int toBePrint = 1;
		TreeNode temp = null;
		while(!queue.isEmpty()){
			temp = queue.poll();
			if(temp.left != null){
				queue.add(temp.left);
				nextLevel++;
			}
			if(temp.right != null){
				queue.add(temp.right);
				nextLevel++;
			}
			list.add(temp.val);
			toBePrint--;
			if(toBePrint == 0){
				toBePrint = nextLevel;
				nextLevel = 0;
				res.add(new ArrayList<>(list));
				list.clear();
			}
		}
		while(!res.isEmpty()){
			result.add(res.pop());
		}
		return res;
	}
}
